package com.gitee.feizns.explore.data_structure.array.easy;

/**
 * 35. 搜索插入位置
 * @author feizns
 * @since 2020/1/7
 */
public class SearchInsert {

    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{1, 2, 3}, 5));
    }

    public static int searchInsert(int[] num, int target) {
        return searchInsert(num, target, 0, num.length - 1);
    }

    public static int searchInsert(int[] num, int target, int l, int r) {
        if ( l > r )
            return l;
        int m = (l + r) / 2;
        if ( target < num[m] )
            return searchInsert(num, target, l, m -1);
        else if ( target > num[m] )
            return searchInsert(num, target, m + 1, r);
        else
            return m;
    }

    //[1,2,3,4,6]

    //

}
